package 我的Java学习_算法基础.day_05;

public class _082_字符串匹配之KMP_上 {
    public static void main(String[] args) {
        String s = "babababcbabababb";
        String key = "bababb";
        int n = indexOf2(s,key);
        System.out.println(n);
    }
    //暴力匹配
    private static int  indexOf(String s,String key){
        int i = 0;  //原串上的指针
        int j=0;    //关键词上指针
        int scanner =i; //扫描指针
        while(scanner<s.length()){
            if(s.charAt(scanner)==key.charAt(j)){
                j++;
                scanner++;
                if(j==key.length())
                    return i;
            }else{
                i++;
                j=0;
                scanner=i;
            }
        }
        return -1;
    }
    //next数组
    private static int indexOf2(String s,String key){
        if(s.length()==0||key.length()==0){
            return -1;
        }
        if(s.length()<key.length()){
            return -1;
        }
        int[] next = next(key);
        int i = 0;
        int j = 0;
        int sLen = s.length();
        int kLen = key.length();
        while(i<sLen){
            if(j==-1||s.charAt(i)==key.charAt(j)){
                i++;
                j++;
            }else{
                j=next[j];
            }
            if(j==kLen){
                return (i-j);
            }
        }
        return -1;
    }

    private static int[] next(String key) {
        int length = key.length();
        int[] next = new int[length];
        char[] p = key.toCharArray();
        next[0] = -1;
        if(length==1){
            return next;
        }
        next[1] = 0;

        int j = 1;
        int k = next[j];//看看j的最长匹配前缀在哪
        while(j<length-1){
            //现在要推出next[j+1]，检查j和k位置上的关系即可
            if(k<0||p[j]==p[k]){
                next[++j]=++k;
            }else{
                k=next[k];
            }
        }
//        for (int e: next
//             ) {
//            System.out.println(e);
//        }
        return next;
    }
}
